1. Field of Invention
This invention relates to a general halftone generation method in digital image systems. A type of algorithm is used which is capable of generating conventional halftone screen patterns as well as novel patterns which can have performance advantages.
2. Background of the Art
Algorithms are needed which can provide a means of simulating a continuous tone image containing a range of gray shades from black to white, or color separation containing a range of densities of some appropriate colorant. The practical implementation of such an algorithm must rely on a dot pattern defined within a fundamental halftone cell or "glyph" which is a relatively small rectangular array of points.
In the art of printing, half-tone systems have long been used to represent pictorial subjects where tone graduation is important. This was and frequently still is accomplished by the use of a photomechanical system in which a fine cross-hatch screen covers the pictorial image during exposure at a suitable stage in the photographic process leading to the printing plate. By this means the image is divided up into a multitude of regularly spaced very small (subliminal) dots whose size varies with the image density being reproduced. With the use of full color printing of subjects, three or four printing plates, one for each of the separate primary color images have to be prepared. The use of identical half-tone screens for each of these color separations can result in undesirable interactive visual effects including very pronounced and objectionable Moire patterns when the several successive print impressions are made. These Moire effects can be reduced to imperceptible levels by crossing the screen directions with one another. In the practice of the art it has long been known that a suitable set of screen angles for four color printing is 45.degree., 0.degree., +15.degree., and -15.degree. (See reference to this art in Chapter 13 of "Principles of Color Reproduction", by J. A. G. Yule, John Wiley & Sons Inc. N.Y., 1967).
In the conventional half-tone system, the original continuous tone picture is represented in the print by regularly spaced high density dots of ink. The dots are sufficiently closely spaced that the unaided human eye cannot distinguish them. The changing size of the dots give the impression of changing tone, and by suitable control of the process the original tones can be reproduced faithfully. With full color originals, suitable control of the process of making the individual half-tone color separations can give faithful reproductions in full color. These photomechanical processes are slow and painstaking, particularly when high quality results requiring considerable manual correction and human judgment are involved.
The transmission of images over telegraph wires based on a process of photoelectric raster scanning was introduced early in the twentieth century. It was also applied to transmitting color images (U.S. Pat. Nos. 2,185,806; 3,413,706). The application of this technique to half-tone plate making by Hardy and others (U.S. Pat. Nos. 2,136,340; 3,190,185; 2,294,644) heralded an era of faster and more automatic plate making and correction. Methods were developed for scanning colored originals (U.S. Pat. Nos. 2,165,168; 2,253,086; 2,571,322) and treating the readings and output by analog devices to produce color separations suitable for color printing plate making with a considerable saving in time.
The combination of these two techniques for the making of color half-tone images was found to suffer from interactive visual effects including the Moire pattern problem known earlier to photomechanical plate makers. Wurzburg (U.S. Pat. No. 2,185,139) made color half-tone separations by the photoelectric raster scanning devices to give different equivalent screen angles for the different colors. Screen angle choice was based on the photomechanical art already existing.
In the photoelectric raster scanning systems, conversion of analogue scanning signals to digital form was found to facilitate manipulation of the signals by computing circuits, as in the electronic formation of half-tone dot patterns (U.S. Pat. No. 3,629,496). Such methods gave color originals suffering from interactive visual effect such as Moire patterns in the resulting prints. Patterns of dots of equal size but with separation distances depending on density in the original were found to reduce the Moire patterns (U.S. Pat. Nos. 3,197,558; 3,580,995) because of the absence of repeating patterns of dots. Direction simulation of the use in color work of four contact screens at different screen angles has been achieved by computing techniques coupled with four different dot generators (U.S. Pat. No. 3,911,480). Choice of the angles used is based on earlier experience with contact screens.
A different approach has been taken to the problems presented by photoelectric scanning methods. This involves the representation of a variable size half-tone dot by a matrix of smaller dots whose number in the matrix is varied to provide half-tone dot size changes and therefore density changes. (U.S. Pat. Nos. 3,604,486; 4,439,789). No change of size or optical density of these smaller dots is involved. Only their presence or absence is considered. This system therefore lends itself to the use of digital signals and their attendant high speed computing means. Enhanced tonal reproduction has been achieved by using a variable pixel area (the area assigned to a single matrix unit) in such matrix systems (U.S. Pat. No. 4,084,259).
In four color printing the separations have been represented by matrix pixels in which the distribution of dots for the same density is varied from one separation to another. This is said to reduce Moire effects (U.S. Pat. No. 3,922,484). This technique of Moire reduction has been expanded by randomizing the distribution of dots in the pixel matrix (U.S. Pat. No. 4,468,706) building on earlier monochrome work (U.S. Pat. No. 3,629,496).
The randomized pixel matrix method of reducing Moire effects has been approached in a separate manner often termed "ordered dither". The raster scan identifies signals corresponding to all the dot positions in the pixel matrix but the presence or absence of a dot in the reproduction is determined by a predetermined matrix of threshold values--one for each dot position in the pixel matrix (U.S. Pat. Nos. 4,193,096; 4,342,051; 4,496,987).
As was reported above, U.S. Pat. Nos. 2,185,139 and 3,911,480 describe raster scan methods to reduce Moire effects which generate half-tone screen dots with different screen angles for the different color separations. This method has been enhanced in U.S. Pat. No. 4,419,690. A variation to this method has been taught in U.S. Pat. No. 4,443,060 wherein quadratic raster meshes of adjacent dots are expanded to contracted in their two diagonal directions. Different expansions/contractions are used for the different color separations.
The non-patent literature contains considerable detailed discussion of the application of raster scanning to half-tone image production. The following papers are representative: "Half-tone method with Edge Enhancement and Moire Suppression", P. G. Roetling, JOSA 66, 985 (1976). In this method, detail corresponding to the spatial frequency of the half-tone screens is suppressed. "Random Nucleated Halftone Screen," J. P. Allebach, PS & E 22.89 (1978). These screens suppress Moire effects by the introduction of random elements.
"An Optimum Algorithm for half-tone Generation for Displays and Hard Copies," T. M. Holladay, Proc. Soc. for Information Display, 21., 185 (1980). This describes electronically produced screens with different screen angles.
"A New Evaluation Method of Image Quality of Digital Halftone Images Obtained by Ordered Dither Method", K. Kinoshita et al., J. Imaging Technology, 10.181 (1984).
U.S. Pat. No. 4,758,886 approaches the problem of Moire fringes in color half-tone images from the standpoint that the mathematical functions describing the half-tone patterns for the individual separations should be orthogonal with one another. These appears to have been no earlier disclosure of such an approach and none of the mathematical investigations in the literature suggest such an approach.
The patent describes a method of designing screen functions for raster-scan generated sets of image comprising two or more color separation images, which sets of generated images have reduced Moire patterns or are free from Moire pattern problems. The method does not use the equivalent of different screen angles for the separations nor is the technique of ordered diether used. The half-tone dot matrixes in a given separation are disposed at a single uniform pitch not at variable pitch as taught in some of the known art.